class Solution:
    def combinationSum4(self, nums: list, target: int) -> int:
        self.nums = nums
        self.searched_dict = dict()
        res = self.search(target)
        return res

    def search(self, yu_num):
        if yu_num not in self.searched_dict:
            mid_res = 0
            for num in self.nums:
                mid = yu_num - num
                if mid == 0:
                    mid_res += 1
                elif mid > 0:
                    mid_res += self.search(mid)
            self.searched_dict[yu_num] = mid_res
            return mid_res
        else:
            return self.searched_dict[yu_num]


a = Solution()
print(a.combinationSum4([1, 2, 3], 4))
print(a.combinationSum4([1, 2, 3], 8))
print(a.combinationSum4([4, 2, 1], 32))
print(a.combinationSum4([], 32))
